# 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
#  岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
#  此外，你可以假设该网格的四条边均被水包围。
#
#  示例 1：
# 输入：grid = [
#   ["1","1","1","1","0"],
#   ["1","1","0","1","0"],
#   ["1","1","0","0","0"],
#   ["0","0","0","0","0"]]
# 输出：1
#
#  示例 2：
# 输入：grid = [
#   ["1","1","0","0","0"],
#   ["1","1","0","0","0"],
#   ["0","0","1","0","0"],
#   ["0","0","0","1","1"]]
# 输出：3
from collections import deque
from typing import List


class Solution:
    def numIslands3(self, grid: List[List[str]]) -> int:
        """
        解法二：并查集
        :param grid:
        :return:
        """
        rows, columns = len(grid), len(grid[0])
        uf = UnionFind(grid)
        for i in range(rows):
            for j in range(columns):
                if grid[i][j] == '1':
                    # grid[i][j] = '0'
                    if i + 1 < rows and grid[i + 1][j] == '1':
                        uf.union(i * columns + j, (i + 1) * columns + j)
                    if j + 1 < columns and grid[i][j + 1] == '1':
                        uf.union(i * columns + j, i * columns + j + 1)
        return uf.counts

    def numIslands2(self, grid: List[List[str]]) -> int:
        """
        解法二：dfs
        遍历整个grid，到遇到'1'时，岛屿数量+1，并将其改为'*'，
        然后dfs将与该'1'相连的所有'1'都变成'*'
        最后再将所有的'*'改回'1'(可以不做)
        :param grid:
        :return:
        """
        rows, columns, res = len(grid), len(grid[0]), 0
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        def dfs(i: int, j: int) -> None:
            if 0 <= i < rows and 0 <= j < columns and grid[i][j] == '1':
                grid[i][j] = '*'
                for x, y in directions:
                    if 0 <= i + x < rows and 0 <= j + y < columns:
                        dfs(i + x, j + y)

        for row in range(rows):
            for column in range(columns):
                if grid[row][column] == '1':
                    res += 1
                    dfs(row, column)
        return res

    def numIslands1(self, grid: List[List[str]]) -> int:
        """
        解法二：bfs(超时)
        遍历整个grid，到遇到'1'时，岛屿数量+1，
        然后bfs将将其改为'*'，并将与该'1'相连的所有'1'都变成'*'
        最后再将所有的'*'改回'1'(可以不做)
        :param grid:
        :return:
        """
        rows, columns, res = len(grid), len(grid[0]), 0
        directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        def bfs(i: int, j: int) -> None:
            q = deque()
            q.append([i, j])
            while q:
                x, y = q.popleft()
                grid[x][y] = '*'
                for x1, y1 in directions:
                    if 0 <= x + x1 < rows and 0 <= y + y1 < columns and grid[x + x1][y + y1] == '1':
                        q.append((x + x1, y + y1))

        for row in range(rows):
            for column in range(columns):
                if grid[row][column] == '1':
                    res += 1
                    bfs(row, column)
        return res

    def numIslands(self, grid: List[List[str]]) -> int:
        return self.numIslands3(grid)


class UnionFind:
    def __init__(self, grid: List[List[str]]):
        rows, columns = len(grid), len(grid[0])
        self.counts = 0
        self.rank = [0] * (rows * columns)
        self.parents = [0] * (rows * columns)
        for i in range(rows):
            for j in range(columns):
                if grid[i][j] == '1':
                    self.counts += 1
                    self.parents[i * columns + j] = i * columns + j

    def find(self, e: int) -> int:
        """
        寻找e的代表元素(父亲),并完成路径压缩
        :param e:
        :return:
        """
        while e != self.parents[e]:
            self.parents[e] = self.parents[self.parents[e]]
            e = self.parents[e]
        return e

    def union(self, e1: int, e2: int) -> None:
        """
        合并两个元素
            1. 分别寻找两个元素的代表元素(父亲)，
            2.判断两个的代表元素是否相同，相同则不需要合并，不同就需要合并
        :param e1:
        :param e2:
        :return:
        """
        root1, root2 = self.find(e1), self.find(e2)
        if root1 != root2:
            self.counts -= 1
            if self.rank[root1] < self.rank[root2]:
                self.parents[root1] = root2
            elif self.rank[root1] > self.rank[root2]:
                self.parents[root2] = root1
            else:  # 秩相等，不仅要更新元素的parent还得更新秩
                self.parents[root2] = root1
                self.rank[root1] += 1


if __name__ == "__main__":
    grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]]
    print(Solution().numIslands(grid))
